package binaryTree.ClosestCommonAncestor;

import binaryTree.TreeNode;

class Class235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int max=p.val>q.val?p.val:q.val;
        int min=p.val<q.val?p.val:q.val;
        return  find(root,min, max);
    }

  /**
   假设val1 < val2，那么val1 <= root.val <= val2
    则说明当前节点就是LCA；若root.val比val1还小，
    则需要去值更大的右子树寻找LCA；若root.val比val2还大，则需要去值更小的左子树寻找LCA。*/
    public  TreeNode find(TreeNode root,int min,int max){
        if (root==null){
            return null;
        }
        if (root.val>max){
            return  find(root.left,min,max);
        }
        if (root.val<min){
            return  find(root.right,min,max);
        }
        return  root;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        treeNode5.left=treeNode3;
        treeNode5.right=treeNode6;
        treeNode3.left=treeNode1;
        treeNode3.right=treeNode4;

        Class235 class235 = new Class235();
        TreeNode treeNode = class235.lowestCommonAncestor(treeNode5, treeNode1, treeNode4);
        System.out.println(treeNode.val);


    }
}

